#include <vector>

using namespace std;

class Solution
{
public:
    // 思路： 摩尔投票法
    // 就是假设数组中有一个众数，我们维护一个候选众数res和一个计数器count。
    // 遍历数组，当遇到与res相同的元素时，count加1；否则，count减1。那么最后res保存的就是众数。
    int majorityElement(vector<int> &nums)
    {
        int res = 0;
        int count = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (count == 0)
            {
                res = nums[i];
            }
            if (nums[i] == res)
            {
                ++count;
            }
            else
            {
                --count;
            }
        }
        return res;
    }
};